//https://leetcode.cn/problems/find-a-good-subset-of-the-matrix/description/?envType=daily-question&envId=2024-06-25


class Solution {
public:
    vector<int> goodSubsetofBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        if(n == 1) {
            for(int j = 0; j < m; j ++) if(grid[0][j]) return {};
            return {0};
        }
        unordered_map<int, int> mp;
        for(int i = 0; i < n; i ++) {
            auto& g = grid[i];
            int key = 0;
            for(int j = 0; j < m; j ++) key = key | (g[j] << j);
            for(int k = 0; k < (int)pow(2, m); k ++) {
                if(((k & key) == 0) && mp.contains(k)) return {mp[k], i}; 
            }
            if(!mp.contains(key)) mp[key] = i;
        }
        return {};
    }
};